      1  import java.awt.Color;

      2  import java.awt.Graphics;

      3  import java.util.concurrent.locks.Lock;

      4  import java.util.concurrent.locks.ReentrantLock;

      5  import javax.swing.JComponent;

      6

      7  /**

      8     This class sorts an array, using the selection sort algorithm.

      9  */

     10  public class SelectionSorter

     11  {

     12     // This array is being sorted

     13     private int[] a;

     14     // These instance variables are needed for drawing

     15     private int markedPosition = -1;

     16     private int alreadySorted = -1;

     17

     18     private Lock sortStateLock;

     19

     20     // The component is repainted when the animation is paused

     21     private JComponent component;

     22

     23     private static final int DELAY = 100;

     24

     25     /**

     26        Constructs a selection sorter.

     27        @param anArray the array to sort

     28        @param aComponent the component to be repainted when the animation

     29        pauses

     30     */

     31     public SelectionSorter(int[] anArray, JComponent aComponent)

     32     {

     33        a = anArray;

     34        sortStateLock = new ReentrantLock();

     35        component = aComponent;

     36     }

     37

     38     /**

     39        Sorts the array managed by this selection sorter.

     40     */

     41     public void sort()

     42           throws InterruptedException

     43     {

     44        for (int i = 0; i < a.length - 1; i++)

     45        {

     46           int minPos = minimumPosition(i);

     47           sortStateLock.lock();

     48           try

     49           {

     50              ArrayUtil.swap(a, minPos, i);

     51              // For animation

     52              alreadySorted = i;

     53           }

     54           finally

     55           {

     56              sortStateLock.unlock();

     57           }

     58           pause(2);

     59        }

     60     }

     61

     62     /**

     63        Finds the smallest element in a tail range of the array

     64        @param from the first position in a to compare

     65        @return the position of the smallest element in the

     66        range a[from]...a[a.length - 1]

     67     */

     68     private int minimumPosition(int from)

     69           throws InterruptedException

     70     {

     71        int minPos = from;

     72        for (int i = from + 1; i < a.length; i++)

     73        {

     74           sortStateLock.lock();

     75           try

     76           {

     77              if (a[i] < a[minPos]) { minPos = i; }

     78              // For animation

     79              markedPosition = i;

     80           }

     81           finally

     82           {

     83              sortStateLock.unlock();

     84           }

     85           pause(2);

     86        }

     87        return minPos;

     88     }

     89

     90     /**

     91        Draws the current state of the sorting algorithm.

     92        @param g the graphics context

     93     */

     94     public void draw(Graphics g)

     95     {

     96        sortStateLock.lock();

     97        try

     98        {

     99           int deltaX = component.getWidth() / a.length;

    100           for (int i = 0; i < a.length; i++)

    101           {

    102              if (i == markedPosition)

    103              {

    104                 g.setColor(Color.RED);

    105              }

    106              else if (i <= alreadySorted)

    107              {

    108                 g.setColor(Color.BLUE);

    109              }

    110              else

    111              {

    112                 g.setColor(Color.BLACK);

    113              }

    114              g.drawLine(i * deltaX, 0, i * deltaX, a[i]);

    115           }

    116        }

    117        finally

    118        {

    119           sortStateLock.unlock();

    120        }

    121     }

    122

    123     /**

    124        Pauses the animation.

    125        @param steps the number of steps to pause

    126     */

    127     public void pause(int steps)

    128           throws InterruptedException

    129     {

    130        component.repaint();

    131        Thread.sleep(steps * DELAY);

    132     }

    133  }